package cn.dglydrpy.study.algorithm.learning.arraySort.quickSort;

import cn.dglydrpy.study.algorithm.learning.utils.LogArithmometer;

/**
 快速排序

 Partition过程
 给定一个数组arr，和一个整数num。请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
 要求额外空间复杂度O(1)，时间复杂度O(N) 

 荷兰国旗问题
 给定一个数组arr，和一个整数num。请把小于num的数放在数组的左边，等于num的数放在中间，大于num的数放在数组的右边。
 要求额外空间复杂度O(1)，时间复杂度O(N)
 
 要求掌握递归和非递归两种方式写出随机快排 
 */
public class Code02_PartitionAndQuickSort {

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	// arr[L..R]上，以arr[R]位置的数做划分值
	// <= X > X
	// <= X X
	public static int partition(int[] arr, int L, int R) {
		if (L > R) {
			return -1;
		}
		if (L == R) {
			return L;
		}
		int lessEqual = L - 1;
		int index = L;
		while (index < R) {
			if (arr[index] <= arr[R]) {
				swap(arr, index, ++lessEqual);
			}
			index++;
		}
		swap(arr, ++lessEqual, R);
		return lessEqual;
	}

	// arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
	// <arr[R] ==arr[R] > arr[R]
	public static int[] netherlandsFlag(int[] arr, int L, int R) {
		if (L > R) { // L...R L>R
			return new int[] { -1, -1 };
		}
		if (L == R) {
			return new int[] { L, R };
		}
		int less = L - 1; // < 区 右边界
		int more = R; // > 区 左边界
		int index = L;
		while (index < more) { // 当前位置，不能和 >区的左边界撞上
			if (arr[index] == arr[R]) {
				index++;
			} else if (arr[index] < arr[R]) {
//				swap(arr, less + 1, index);
//				less++;
//				index++;						
				swap(arr, index++, ++less);
			} else { // >
				swap(arr, index, --more);
			}
		}
		swap(arr, more, R); // <[R]   =[R]   >[R]
		return new int[] { less + 1, more };
	}

	/**
	 *  快排V1.0
	 *  在arr[L..R]范围上，进行快速排序的过程：
	 *  1）用arr[R]对该范围做partition，<= arr[R]的数在左部分并且保证arr[R]最后来到左部分的最后一个位置，记为M； <= arr[R]的数在右部分（arr[M+1..R]）
	 *  2）对arr[L..M-1]进行快速排序(递归)
	 *  3）对arr[M+1..R]进行快速排序(递归)
	 *  因为每一次partition都会搞定一个数的位置且不会再变动，所以排序能完成
	 * @param arr
	 */
	public static void quickSort1(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process1(arr, 0, arr.length - 1);
	}

	public static void process1(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		// L..R partition arr[R] [ <=arr[R] arr[R] >arr[R] ]
		int M = partition(arr, L, R);
		process1(arr, L, M - 1);
		process1(arr, M + 1, R);
	}


	/**
	 快排V2.0
	 在arr[L..R]范围上，进行快速排序的过程：
	 1）用arr[R]对该范围做partition，< arr[R]的数在左部分，== arr[R]的数中间，>arr[R]的数在右部分。假设== arr[R]的数所在范围是[a,b]
	 2）对arr[L..a-1]进行快速排序(递归)
	 3）对arr[b+1..R]进行快速排序(递归)
	 因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成


	 快排V1.0和V2.0 数组已经有序的时候就是复杂度最高的时候
	 时间复杂度O(N^2)
	 */
	public static void quickSort2(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process2(arr, 0, arr.length - 1);
	}

	// arr[L...R] 排有序，快排2.0方式
	public static void process2(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		// [ equalArea[0]  ,  equalArea[0]]
		int[] equalArea = netherlandsFlag(arr, L, R);
		process2(arr, L, equalArea[0] - 1);
		process2(arr, equalArea[1] + 1, R);
	}


	/**
	 快速排序V3.0(随机快排+荷兰国旗技巧优化)
	 在arr[L..R]范围上，进行快速排序的过程：
	 1）在这个范围上，随机选一个数记为num，
	 1）用num对该范围做partition，< num的数在左部分，== num的数中间，>num的数在右部分。假设== num的数所在范围是[a,b]
	 2）对arr[L..a-1]进行快速排序(递归)
	 3）对arr[b+1..R]进行快速排序(递归)
	 因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成

	 快速排序V3.0时间复杂度:
	 1）通过分析知道，划分值越靠近中间，性能越好；越靠近两边，性能越差
	 2）随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件
	 3）把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N
	 4）那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望！
	 时间复杂度O(N*logN)，额外空间复杂度O(logN)都是这么来的。
	 */
	public static void quickSort3(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process3(arr, 0, arr.length - 1);
	}

	public static void process3(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
		int[] equalArea = netherlandsFlag(arr, L, R);
		process3(arr, L, equalArea[0] - 1);
		process3(arr, equalArea[1] + 1, R);
	}

	// for test
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = LogArithmometer.generateRandomArray(maxSize, maxValue);
			int[] arr2 = LogArithmometer.copyArray(arr1);
			int[] arr3 = LogArithmometer.copyArray(arr1);
			quickSort1(arr1);
			quickSort2(arr2);
			quickSort3(arr3);
			if (!LogArithmometer.isEqual(arr1, arr2) || !LogArithmometer.isEqual(arr2, arr3)) {
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Oops!");

	}

}
